#!/usr/bin/env python3
# -*- coding: utf-8 -*-

# 题目：二分查找（给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target  ，
# 写一个函数搜索 nums 中的 target，如果目标值存在返回下标，否则返回 -1。）

# 解题思路：定义左右边界left， right，找到中间值，然后三种情况：
# 1.如果中间值mid 比目标值target大，说明目标值在中间值左边，此时right = mid - 1. 因为 mid肯定不是目标值，所以减一
# 2.如果中间值mid 比目标值target小，说明目标值在中间值右边，此时left = mid + 1. 因为 mid肯定不是目标值，所以加一
# 3.中间值mid与目标值target相等，就说明目标值找到了，返回mid

class Solution:
    def search(self, nums, target):
        left, right = 0, len(nums) - 1   #获取下标
        while left <= right:
            middle = (right - left) // 2 + left
            if nums[middle] > target:
                right = middle - 1
            elif nums[middle] < target:
                left = middle + 1
            else:
                return middle
        return -1